<!doctype html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <meta name="viewport"
          content="width=device-width, user-scalable=no, initial-scale=1.0, maximum-scale=1.0, minimum-scale=1.0">
    <meta http-equiv="X-UA-Compatible" content="ie=edge">
    <title>Document</title>
</head>
<body>
<script>
    /*
    * 1.递归函数
    *   递归：每次递出去的，最终都要拿回来
    *   思想：将一个复杂问题，分解成若干个简单的问题，然后重复下去并解决掉
    *
    *   1.将问题抽象成为递归的问题
    *
    *   2.写出函数解决它
    *
    * */

    //高斯定理 1加到100 1 + 2 + 3 + ... + 100
    //实现一个函数sum(n) 返回 1+2+3+...+n的和
    //1.想一个问题：sum多少可以直接算出来？sum(1)可以直接算出来，sum(1) = 1
    //2.sum(n) = [1 + 2 + 3 +...+ (n-1)] + n
    //3.sum(n-1) = 1 + 2 + 3 +... + (n-1)
    //4.对比sum(n)等式中[]内的内容，和sum(n-1)等式的内容一模一样
    //5.所以sum(n) = sum(n-1) + n 就等价于要求sum(n-1)的和再加上一个n就行了

    function sum(n){ //计算sum(n)的和
        if(n === 1) return 1 //sum函数的结束条件，return 1结束的是哪个函数？结束的是sum(1)的函数，
        //递归自己套自己套了n个函数，所以要得出并返回最终的那个函数，就必须先解决最基本的函数的答案
        return sum(n-1) + n //sum(n)的和等于 sum(n-1) + n ，就等价于要求sum(n-1)的和再加上一个n就行了
    }
    /*
    * sum(4) = sum(3) + 4
    * sum(3) = sum(2) + 3
    * sum(2) = sum(1) + 2
    * sum(1) = 1
    *
    * 所以
    * sum(4) = (((1 + 2) + 3) + 4)
    *
    * */

    //1^5 + 2^5 + 3^5 +...+n^5
    //用sum2(n)解决上述问题 请实现这个函数sum2(n)

    /*
    * 按照刚刚的思路 哪个函数可以一下子得出答案？
    * 1.当然是最基本的那个sum2(1) = 1^5 = 1
    * 2.sum2(n)可以拆成两部分，即前(n-1)项的和加上n的5次方，就是sum2(n) = sum2(n-1) + Math.pow(n,5)
    *
    * */
    function sum2(n){
        if(n === 1) return 1 //结束条件，结束最基础函数sum2(1)的情况
        return sum2(n-1) + Math.pow(n,5) //返回sum2(n)的结果，等于前(n-1)项的5次方和 再加上n的5次方
    }


    //new Array(10) //生成一个长度为10的数组 返回值是10个值为undefined的空占位[empty * 10]
    //new Array(10).fill(0) //就是给这个长度为10的数组全部填充上值0，fill里面传一个参数表示填充的固定值是什么，还阔以传开始位置和结束位置
    //[0,0,0,0,0,0,0,0,0,0]

    let s = new Array(10).fill(0).map((i,j)=>(j+1)**5).reduce((total,item)=>total+item)
    //new生成一个长度为10的数组，fill给这个数组每个元素填充固定值为0，在map方法中传入一个回调函数即箭头函数，箭头函数接收的参数为元素i和元素下标j
    //下标是从0开始所以要每个元素(下标+1)**5次方，分别得出这10个元素的5次方值，用reduce方法迭代，在reduce方法中传入一个回调函数即箭头函数，
    //回调函数接收两个参数迭代体total和元素item，每次迭代都是上次的迭代结果total加上下一个元素item，最后将返回的最终值赋值给s变量接收
    //上面的这行代码等价于下面的这一行函数执行
    console.log(sum2(10))
    console.log(s)

    //求阶乘 f(n) = 1*2*3*...*n
    /*
    * 已知阶乘 f(1) = 1
    *
    * 因为 f(n) = 1*2*3*...*(n-1)*n
    *
    * 又因为 f(n-1) = 1*2*3*...*(n-1)
    *
    * 所以 f(n) = f(n-1)*n
    * */
    function factorial(n){
        if(n === 1) return 1 //结束条件，1的阶乘是1，return结束的是f(1)的情况
        return factorial(n-1) * n //递归内容 f(n) = f(n-1)*n 会一步步分解至我们已知值得f(1) 要得出最终的f(n) 就要得出最基本的f(1)的值 最终递归回去
    }

    console.log(factorial(7))


    /*
    * 斐波拉契 的第n项
    * 斐波拉契数列 每一项等于前两项之和
    * 1 1 2 3 5 8 13 21 ...
    *
    * */

    /*
    * 已知前两项的结果都为1
    * f(1) = 1
    * f(2) = 1
    * 假设 f(n) 表示第n项的值 根据规律任意一项等于前两项的和 可得出下列公式
    * f(n) = f(n-2) + f(n-1)
    * 如果递归没有记忆 就会消耗很多时间来计算结果
    *
    * */
    let list = {} //创建一个对象，表示将之前算的结果，都存储到这个对象中
    function fb(n){ //这个函数很有问题 相同的一项会被重复算两次 所以要做个表记录
        if(list[n]) return list[n] //表示如果有已经算出来的结果 就直接查表
        if(n < 3) {
            list[n] = 1 //对象[属性名] = 属性值 表示在对象{}中 将属性名为的1的属性值赋值为1 将属性名为的2的属性值赋值为1
            return list[n] //结束条件 return的是n小于等于2的两个情况的值
        }
        list[n] = fb(n-2) + fb(n-1)
        return list[n] //只要解决了最基本的前两项fb(1)和fb(2)的值 一层层往上就能得到第n项的值
    }
    //f(40) = f(39) + f(38)
    //f(39) = f(38) + f(37) //f(38)被算了两次 很浪费时间

    console.log(fb(25))



</script>
</body>
</html>